The present invention is part of a new and improved computer system, parts of which are described in other related applications. The computer system bus basic arbitration protocol is described in U.S. application Ser. No. 07/436,144 filed Nov. 13, 1989 by Ross M. Wille and Richard J. Carter entitled "Distributed Fair Arbitration Scheme for Providing Access to a Data Communication Bus", now U.S. Pat. No. 5,151,994.
The computer system incorporates a bus with four control states described in U.S. application No. 7,694,265 filed Apr. 29, 1991 by William Jaffe, Russell C. Brockmann and Leith Johnson entitled "Quadrature Bus Protocol for Carrying Out Transactions in a Computer System" (hereinafter called the Jaffe-1 application). The computer memory has a block interleaving scheme described in U.S. application Ser. No. 07/679,868 filed Apr. 3, 1991 by Russell C. Brockmann, William Jaffe and William Bryg entitled "Flexible N-way Memory Interleaving" (hereinafter called the Brockmann-1 application). Communication with slow devices is described in U.S. application No. 07/705/873 filed May 28, 1991 by Russell C. Brockmann, William Jaffe and Leith Johnson entitled "Method of Reducing Wasted Bus Bandwidth Due to Slow Responding Slaves in a Multiprocessor Computer System". All of these applications are specifically incorporated herein by reference for all that they teach. The present invention comprises improvements in memory system performance and design of the systems disclosed in these applications.
Modern computer systems often have a plurality of "intelligent" devices interconnected by a high speed communications link. Within a single computer, multiple processors may use an internal data bus to communicate with each other, with peripheral I/O devices and with shared memory subsystems. A transaction is a communication between two devices. A device requesting access to the bus is called a master. The target device of the transaction is called a slave. An arbitration method, also called an arbitration protocol, determines which requesting device gains access to the bus when multiple devices simultaneously contend for access.
In most computer systems, memory transactions comprise the overwhelming majority of transactions between devices. Processors send data to memory and retrieve data from memory. Peripheral I/O devices send data directly to memory or receive data directly from memory via direct memory access (DMA). Therefore, optimization of memory transactions is a critical element in obtaining good system performance. A typical memory transaction consists of a master device sending a memory address to a memory subsystem followed by the memory slave device sending data from that address to the requesting master device.
In the simplest systems, the entire system waits for the completion of a memory transaction before any other transactions can be initiated. In pipelined systems, multiple transactions can be in process simultaneously. For example, multiple requests for memory may be initiated before the first request is completed. In split protocol systems, sending the address and sending the data are separate transactions. In split protocol systems, the requesting master device arbitrates for access to the bus, sends the memory address and read command to the slave memory device, and then releases the bus. The memory device then processes the request, arbitrates for access to the bus, and sends the data back to the requesting master device. This split transaction frees the bus for other transactions during the memory latency period.
A particular memory subsystem may be the target of several consecutive or closely spaced memory transactions. In a split protocol system, memory systems typically employ a queue to store these requests. In any practical system, the depth of the queue is limited. If the input queue is full, the system must then provide a mechanism for the slave to notify the master that a requested transaction cannot be completed. On notification of a "busy" slave, the master will typically wait some defined amount of time and repeat the transaction. There is usually some companion strategy or rule to guarantee that the master will eventually complete its transaction.
In addition to a request queue, the memory controller may also employ an output queue. This allows the memory controller to place read data into a buffer pending successful arbitration of the bus. During this arbitration and eventual forwarding of data to the requesting master, the memory controller is free to begin processing the next request it may have in its request queue.
In the discussion above, the transaction involves a master device requesting data from memory. A memory transaction may instead entail a master device sending data to be stored into memory. In this case, the address is followed by data to be stored. The memory system typically needs an input queue for input data. The memory system then requires time to store received data before the memory system is available for another transaction.
In the system described above, masters will often gain access to the bus only to find that the target slave is busy. This "busy" transaction wastes time for the requesting master and ties up the bus, preventing useful access by other devices. Additionally, request queues, output queues, input queues and arbitration circuitry all add latency time, cost and complexity to memory subsystems. Hence, there is a need to improve performance by eliminating busy transactions and to improve the latency time of memory subsystems by elimination of queues. Also, there is a need to reduce the cost and complexity of memory subsystems by elimination of arbitration circuitry and queues.